package 链表系列;

import jdk.nashorn.internal.runtime.JSONListAdapter;

public class RemoveNthFromEnd {
    //两趟扫描
//    public ListNode removeNthFromEnd(ListNode head, int n) {
//        ListNode dummyHead = new ListNode(-1,head); //虚拟头节点
//
//        ListNode cur = dummyHead;   //当前节点
//        int cnt = 0;
//        while(cur.next!=null){  //第一遍扫描，找到有多少个元素
//            cur = cur.next;
//            ++cnt;
//        }
//        int num = cnt - n;
//        int i = 0;
//        cur = dummyHead;
//        while(i<num){   //第二遍扫描，找到第num个元素,即要删除元素的前一个元素
//            cur = cur.next;
//            i++;
//        }
//        cur.next = cur.next.next; //删除元素
//        return dummyHead.next;
//    }

    //一遍扫描（双指针法）
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummyHead = new ListNode(-1,head); //虚拟头节点

        ListNode fast = dummyHead;      //快指针
        ListNode slow = dummyHead;      //慢指针

        while(n-- >0 && fast!=null){    //先让快指针前进n格，这样慢指针和快指针的差距就为n格
            fast = fast.next;
        }
        fast = fast.next;               //这里fast前进一格是为了让slow指向要删除节点的前一个节点，方便删除
        while (fast!=null){             //这里让fast前进到最后一个节点，从而得到的slow和fast之前差了n+1个节点，即为倒数第n+1个
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;     //删除操作
        return dummyHead.next;
    }
}
